#include <stdio.h>
#include <stdlib.h>
#include "heap.h"

int pq_parent(int n)
{
	if (n == 1)
		return(-1);
	else
		return((int) n/2);
}

int pq_young_child(int n)
{
	return(2 * n);
}

void pq_insert(priority_queue *q, queue_element x)
{
	if (q->n >= q->PQ_SIZE)
		printf("Warning: priority queue overflow insert\n");
	else 
	{
		q->n = (q->n) + 1;
		q->q[ q->n ] = x;
		bubble_up(q, q->n);
	}
}

void bubble_up(priority_queue *q, int p)
{
	if (pq_parent(p) == -1) 
		return; /* at root of heap, no parent */

	if (q->q[pq_parent(p)].val > q->q[p].val) {
		pq_swap(q,p,pq_parent(p));
		bubble_up(q, pq_parent(p));
	}
}
void pq_swap(priority_queue *q, int p, int parent)
{
	queue_element temp;

	temp = q->q[p];
	q->q[p] = q->q[parent];
	q->q[parent] = temp;
}
	
void pq_init(priority_queue *q, int size)
{
	q->n = 0;
	q->PQ_SIZE = size;
	q->q = 
		(queue_element *) malloc(sizeof(queue_element) * (q->PQ_SIZE + 1));
}

void make_heap(priority_queue *q, queue_element s[], int n)
{
	int i;
	/* counter */
	pq_init(q,n);
	for (i=0; i<n; i++)
		pq_insert(q, s[i]);
}

queue_element extract_min(priority_queue *q)
{
	queue_element min;
	min.val = -1;
	/* minimum value */
	if(pq_is_empty(q))
	{
		min.stream_index = -1;
		return min;
	}
	else 
	{
		min = q->q[1];
		q->q[1] = q->q[ q->n ];
		q->n = q->n - 1;
		bubble_down(q,1);
	}

	return(min);
}

int pq_is_empty(priority_queue *q)
{
	if (q->n <= 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

void bubble_down(priority_queue *q, int p)
{
	int c;
	/* child index */
	int i;
	/* counter */
	int min_index;
	/* index of lightest child */
	c = pq_young_child(p);
	min_index = p;
	for (i=0; i<=1; i++)
		if ((c+i) <= q->n) {
			if (q->q[min_index].val > q->q[c+i].val) min_index = c+i;
		}
	if (min_index != p) {
		pq_swap(q,p,min_index);
		bubble_down(q, min_index);
	}
}

void heapsort(queue_element s[], int n)
{
	int i;
	priority_queue q;
	/* counters */
	/* heap for heapsort */
	make_heap(&q,s,n);
	for (i=0; i<n; i++)
		s[i] = extract_min(&q);
}
